\documentclass[UTF8]{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{ctex}
\setlength{\parindent}{2em}

\title{Homework 7:Bellman Ford算法的实现}

\author{唐瑞良\\ 强基工程力学 3210105852}

\begin{document}

\maketitle
\section{设计思路}
\indent 算法核心就那几行，不多说了。\\
\indent 对于效率验证，首先我作了$Random\_Graph$使得程序能够生成随机图。它的实现方式是通过给定节点数生成边，共经过总节点数$^2$次循环，每次循环如果遇到首尾相同的情况，则默认为0。对于正常情况，采用生成介于$0~1$的小数与$\frac{剩余需要生成的边数}{剩下至多能够生成的边数}$作比较，如果前者小于后者，那么选择生成这条边，边权为介于$-500~500$之间的整数，总之，这是一种通过概率生成图的方案。\\
\indent 而后我创建了两个函数$test\_Vsame$和$test\_Esame$,他们的作用是在节点数相同时不断改变边数进行测试，另一种则是在边数相同时不断改变节点数进行测试，经过测试，运行时间分别与V和E的数目呈线性关系，可以验证时间复杂度为$O(VE)$。\\
\section{改进思路与补充说明}
\indent 在算法实现时的$n-1$次循环中，可以添加比较：上一次的结果与这一次结果的比较。如果二者相同，可提前结束循环。\\
\indent 这次采用了邻接表进行测试，之前采用邻接矩阵的方法需要对两个点之间是否相连做比较，它占用的时间是不能够忽略的。于是在测试中跑出了$O(V^3)$的时间复杂度。另外观察到通过使用邻接矩阵做固定V的测试时，出现了形如$\frac{lnx}{x}$这样的先递增再递减最终趋于一个常数的曲线，原因不明。\\
\section{测试结果}
\begin{center}
\begin{figure}
\includegraphics{固定V.PNG}
\caption{固定$V=1000$时运行时间与边数的关系}
\end{figure}
\begin{figure}
\includegraphics{固定E.PNG}
\caption{固定$E=400000$时运行时间与节点数的关系}
\end{figure}
\end{center}
\end{document}
